moddbfandomcom-20200213-history
AI techniques overview
This is an overview of techniques used inside a game's AI. For an overview of the topic generally, see Artificial intelligence. For more details on a particular technique, see the technique's main page. See also Artificial Intelligence at Wikipedia Goals of AI Artificial intelligence is an attempt to provide in-game characters with life-like behavior. This life-like behavior can be as simple as moving a paddle from side to side, as seen in Pong. It can be seen as a character moving between two places in the game. It can be complex, perhaps giving what appears to be a life-like personality to thousands of bloodthirsty orcs as they wage war across the countryside, using many different weapons and countless attack styles, fighting in seeming mortal combat the personalities of the defenders of the land each with different weapons. One of the frequent goals of AI is to introduce randomness to the game. It is not life-like behavior to follow the perfect path every time. It is not life-like behavior to have 100% accuracy and precision on every target. It is not life-like behavior to always know every detail and always take the perfect reaction. Consequently, most artificial intelligence techniques take advantage of number generators to disturb the otherwise perfect behaviors. Pathfinding Perhaps the most visible AI technique is pathfinding. At a basic level it involves moving game entities from point A to point B along a reasonable path. Path finding is reducible to a graph search algorithm. * A* (pronounced "A star") is a very effective algorithm and frequently used in games. A* is a greedy algorithm that uses a heuristic to guess at the ideal next move. * Dijkstra's algorithm searches distances to all points rather than the best path to a single point. Dijkstra's algorithm can be implemented in terms of A* by providing a zero-value heuristic and enough time and space for a complete search. * B* is similar to A* in operation and performance. It is functionally similar, but operates as a tree rather than a connected graph. * Floyd-Warshall algorithm can find the shortest path between all pairs of a weighted, directed graph. * Gradient Descent and Hill Climbing algorithms consider only the neighboring points and moves incrementally toward the best nearby location. When determining the paths to follow, the pathfinding algorithms can employ additional collision avoidance techniques to avoid obstacles such as trees, water, bridges, or other features. This might include a sphere of influence around objects. It might also include a network of key nodes that should be used for complex searches such as known paths between significant points, like traveling along a narrow bridge or between frequently visited rooms. These algorithms also frequently use weighted edges to make certain paths less desirable than others. For example, a straight path is generally preferable to continuously moving back and forth along diagonals. As another example, wide turns around corners toward the middle of the path generally provides a more life-like behavior than holding close to a wall and turning at a right angle when reaching the corner. Flocking Flocking is the process of encouraging a group of actors to exhibit similar behaviors to each other, yet still operate independently. The implementation of flocking behavior will depend on how you implement other subsystems of your game. One common approach is to assign all the actors in the flock to a common element. By implementing a few simple rules one can design an effective flocking system. Here is one example: *Rule 1: Do not collide with neighbors. Avoid it at all costs. *Rule 2: Attempt to reach the goal. Move there as fast as reasonable, considering rule 1. *Rule 3: Attempt to travel at the same speed as your closest neighbors. This simple set of flocking behavior is effective for birds, fish, and many other types of flocks. A small set of carefully chosen rules can provide complex behavior systems. State machines for AI State machines are a mainstay of computer science, and are used for many in-game features. When used in AI, an actor will operate in a specific state. Events occur that cause the actor to transition from one state into another. The states could be a convoluted graph with many points, or it could be a simple list of states that are considered in order. For example: *Idle State **Look around **If you see opponent, go to Attack State **If you near injured temamate, go to Heal State **Otherwise, go to Idle State *Attack State **If critically injured, go to Run Away State **If opponent visible, go to Fire State **If no opponent visible, go to Idle State *Heal State **If self critically injured, heal self and repeat **If teammate critically injured, heal teammate and repeat **If self injured, heal self and go to Idle State **If teammate injured, heal teammate and go to Idle State *Other states follow... State management can be expressed easily in most programming languages, making them easy to implement, maintain, and extend. Debugging state machines is often just as trivial as maintaining a very small inheritance hierarchy. They can easily be tuned and adjusted by non-programmers, empowering designers, producers, QA leads, and even end users to safely adjust them (freeing programmers for more important tasks). State machines can be created so that every piece of new content enables the states of other elements -- which means add-ons and expansions packs are easier. State machines are widely understood by programmers, and are taught in theory classes in nearly every Computer Science program. Because of these reasons and many more, state machines are usually the preferred choice for AI. Rule Based AI / Expert System Expert systems consist of a set of rules and an inference engine. The game engine passes the current actor's "knowledge" (the local environment, the actor's recent memory, etc) to the inference engine. The inference engine compares the knowledge with all known rules. When a piece of knowledge matches a rule, then any knowledge already attached to the rule is added to the search tree. If that piece of knowledge has an instruction or command associated, that command is triggered. The engine may use depth-first, breadth-first, or a hybrid approach at searching the tree. Example: Rules: *(GOLD) is (GETTABLE) *(WEAPON) is (GETTABLE) *(ARMOR) is (GETTABLE) *(ARMOR AC) > (MY ARMOR AC) is (WANTED) *(WEAPON DAMAGE) > (MY ARMOR DAMAGE) is (WANTED) *(GOLD) is (WANTED) *if (GETTABLE) and (WANTED) then MoveToAndCollect *if (ARMOR) and (WANTED) then SwapArmor *if (WEAPON) and (WANTED) then SwapWeapon Comprehensive rules systems are difficult to create and can take a lot of computing power, so these are not frequently used in games. Artificial Neural Networks Artificial Neural Networks are a way to learn functions from inputs to outputs. Feedback from ”training data” and real examples is used to modify the function to better match the desired outputs. The classic example is the Perceptron (wikipedia). In the simple case of a Perceptron, you consider a single input and get a single result. A single Perceptron can solve a single binary classification. For example, it might say: bool Perceptron (x) { if (0 < ( s * x + b )) return true; return false; } This simple Perceptron indicates if the input is above or below a given line, with slope s and bias b. The process of configuring the slope and bias is called "training". While the machine is trained, it requires feedback to see if the output is right or wrong. If the output is wrong the program must modify either the slope or the bias in order to generate a better result next time. If the output is correct, the program might (or might not) choose to modify the slope or bias to improve the results. Artificial Neural Networks are very efficient at recognizing patterns, including mouse and pen gestures. By providing only a few parameters about a pen stroke, for example, it is possible to recognize the entire Graffiti text system with almost no processing power. Unfortunately, training the networks with a sufficiently large training set can take some time. Most real-world training sets cannot be completed within a normal interactive game speed. However, once trained, most networks are able to provide extremely accurate high speed recognition results. Reinforcement Learning Reinforcement learning is a technique for associating present rewards and punishments with past actions. It then relies on function approximation (neural networks or other techniques) to estimate the effect of the present on the future. An AI continually learns (associates present rewards with past actions), and also uses the knowledge it has learned to make decisions (present actions estimate future rewards). Learning can take place while the game is being placed, but also can take place between repeated games, to model the AI's version of the way a human player gets better by playing many games. Simulated Annealing Simulated Annealing is a technique for optimization, modeled on the cooling of metal atoms in an alloy. First, points are chosen across the parameter space. Then, in successive steps, the “energy” (heat) of the system is lowered. The energy level influences how quickly the points move in parameter space. The points move towards more optimal parameters. As the system cools, the step size shrinks, and the points move less and less, until finally, they settle on their local optimum points. Then a final scan over the points finds the global optimum. Genetic Algorithms Genetic algorithms also are a technique for optimization, modeled on the principles of genetic mutation. Unlike simulated annealing, the set of points is not fixed. Instead, points that are worse are culled, and points that are better are cloned. Following cloning is mutation (random change) and crossover (mixing portions of one point with portions from another point). For genetic algorithms to work, the points must be structured — for example, an array of floats — so that crossover can have a meaningful definition of “partial”. The biological inspiration and interpretation of this process is that culling is like an unfit organism dying; cloning is an organism giving birth; mutation is something that happens in nature to DNA; and crossover is sexual reproduction. Simulated annealing and genetic algorithms are useful for optimizing problems for which there aren't good algorithms. They are usually slower than optimization techniques like linear programming, but faster than an exhaustive search over the parameter space. Summary This is an incomplete overview of a few AI topics. The field is relatively new and is always growing. Most topics in Artificial Intelligence are actively being researched across many industries. Each specific topic is nuanced with their own unique benefits and challenges. Each specific topic can be -- and most have been -- studied and researched at the doctorate levels of computer science and mathematics. However many of the academic studies are not directly solving the problems encountered in computer games. Challenges Perhaps the biggest challenge with AI techniques are that they are very compute intensive. For many games, AI is allowed the second-most processing time, with rendering being allowed slightly more. Each of the techniques mentioned above can eat all the processing power available to them, and more. Some games, such as Go and chess, provide incredible challenges to even the most powerful supercomputers. Bringing these systems into real-time interactive games is a great challenge, and will be an interesting challenge for many years to come. Category:Artificial intelligence